﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace Hands.Queue
{
    public sealed class ConcurrentLinkedQueue<T> where T : class
    {
        private class Node<E>
        {
            internal T data;
            internal Node<E> next;

            internal Node(T data, Node<E> next)
            {
                this.data = data;
                this.next = next;
            }
        }
        private const int ADDEND = 1;
        private const int QUEUE_EMPTY = 0;

        private Node<T> head;
        private Node<T> tail;

        private AtomicInteger length = new AtomicInteger(QUEUE_EMPTY);

        public bool IsEmpty
        {
            get
            {
                return this.head.next == null;
            }
        }

        public int Length
        {
            get
            {
                return length.get();
            }
        }

        public ConcurrentLinkedQueue()
        {
            this.head = new Node<T>(null, null);
            this.tail = head;
        }

        /// <summary>
        /// 入队列(线程安全)
        /// </summary>
        /// <param name="data">要加入队列的数据</param>
        /// <returns>加入成功则返回true，失败返回false</returns>
        public bool put(T data)
        {
            //非阻塞算法请参考：http://www.ibm.com/developerworks/cn/java/j-jtp04186/

            Node<T> node = new Node<T>(data, null);
            do
            {
                //保存当前队列的尾节点的指针
                Node<T> currentTail = this.tail;
                //保存当前尾节点的下一个节点的指针
                Node<T> residue = currentTail.next;
                //判断当前尾节点是否被修改过
                if (currentTail == this.tail)
                {
                    //判断尾指针后是否被添加了新指针
                    if (residue == null)
                    {
                        //将新节点插入到当前尾节点后面
                        if (Interlocked.CompareExchange<Node<T>>(ref currentTail.next, node, null) == null)
                        {
                            //移动尾指针
                            bool result = Interlocked.CompareExchange<Node<T>>(ref this.tail, node, currentTail) == currentTail;
                            length.addAndSet(ADDEND);
                            return result;
                        }
                    }
                }
                else
                {
                    //若已经有新指针插入，则先移动尾指针到新的尾节点
                    Interlocked.CompareExchange<Node<T>>(ref this.tail, residue, currentTail);
                }
            }
            while (true);
        }

        /// <summary>
        /// 从当前队列的第一个元素
        /// </summary>
        /// <returns>当前队列的第一个元素</returns>
        ///<exception cref="">若队列为空，抛出NullReferenceException异常</exception>
        public T get()
        {
            Node<T> currentHead = this.head.next;
            this.head = currentHead;
            length.subtractAndSet(ADDEND);
            return currentHead.data;
        }
    }
}
